\documentclass{article}
\usepackage{indentfirst}
\usepackage[fontset=windows]{ctex}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{times}
\usepackage{mathptmx}
\usepackage{indentfirst}
\usepackage[noend]{algpseudocode}
\usepackage{algorithmicx,algorithm}
\usepackage{subfigure}
\usepackage{graphicx}
% \usepackage{pythonhighlight}
% 设置页面格式
\geometry{left=31.7mm,right=31.7mm,top=25.4mm,bottom=25.4mm}
\pagestyle{plain}
\linespread{1}
\setlength{\parindent}{2em}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setCJKfamilyfont{zhsong}[AutoFakeBold = {3.17}]{SimSun}
\renewcommand{\songti}{\CJKfamily{zhsong}}
\setCJKfamilyfont{zhhei}[AutoFakeBold = {3.17}]{SimHei}
\renewcommand{\heiti}{\CJKfamily{zhhei}}
% 新命令%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\zhengwen}{\zihao{-4}\songti}
\newcommand{\tuti}{\zihao{-4}\heiti}
\newcommand{\biaoti}{\zihao{5}\heiti}
\newcommand{\zhaiyao}[1]{\zihao{-4}\heiti\textbf{【摘要】}\songti\zihao{-4}{#1}\\}
\newcommand{\guanjianzi}[1]{\zihao{-4}\heiti\textbf{【关键字】}\songti\zihao{-4}{#1}\\}
\newcommand{\timu}[1]{\centerline{\zihao{3}\heiti\textbf{#1}}}
\newcommand{\abstracthead}[1]{\zihao{-4}\heiti\textbf{【Abstract】}\zihao{-4}\setmainfont{Times New Roman}{#1}\\}
\newcommand{\keyword}[1]{\zihao{-4}\heiti\textbf{【Key words】}\zihao{-4}\setmainfont{Times New Roman}\textbf{#1}\\}

\newcommand{\yiji}[1]{\flushleft{\zihao{4}\textbf{\heiti{#1}}}}

\newcommand{\erji}[1]{\flushleft{\zihao{-4}\textbf{\heiti{#1}}}}

\newcommand{\sanji}[1]{\flushleft{\zihao{-4}\textbf{\songti{#1}}}}
\renewcommand*{\paragraph}{\hspace{2em}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}  	%高亮使用的颜色
\usepackage{accsupp}	
\usepackage{listings}
%下面的是配置是可以写中文注释的python环境:
	%\usepackage{listings}
	%\usepackage{color}
	\definecolor{dkgreen}{rgb}{0,0.6,0}
	\definecolor{gray}{rgb}{0.5,0.5,0.5}
	\definecolor{mauve}{rgb}{0.58,0,0.82}
	\lstset{	frame=shadowbox,                           % shadowbox framed
		rulesepcolor= \color{gray},%框的颜色
		language=Python,
		aboveskip=3mm,
		belowskip=3mm,
		showstringspaces=false,
		columns=flexible,
		basicstyle={\small\ttfamily},
		numbers=left,%设置行号位置none不显示行号
		%numberstyle=\tiny\courier, %设置行号大小  
		numberstyle=\tiny\color{gray},
		keywordstyle=\color{blue},
		commentstyle=\color{dkgreen},
		stringstyle=\color{mauve},
		breaklines=true,
		breakatwhitespace=true,
		escapeinside=``,%逃逸字符(1左面的键)，用于显示中文例如在代码中`中文...`
		tabsize=4,
		extendedchars=false %解决代码跨页时，章节标题，页眉等汉字不显示的问题  
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\timu{题目}
~\\
\hrule

~\\
\zhaiyao{这里书写摘要}
\guanjianzi{在这里书写关键字}
\abstracthead{write abstract here}
\keyword{write keywords here}
\rule[0pt]{15.32cm}{0.05em}
\yiji{一级标题}
\erji{二级标题}
\sanji{三级标题}

\zhengwen
~\\
\paragraph
当数据点的分布可以用类似椭圆球形的形状来划分簇的话，那么高斯聚类是比较理想的，高斯分布密度函数为：

$$
g(x;\mu,\sigma)=\frac{1}{\sqrt{(2\pi)^d|\sigma|}}e^{-\frac{1}{2}(x-\mu)^T\sigma^{-1}(x-\mu)}
$$

\paragraph
这个式子与单维变量形式的高斯密度函数类似，是针对多维空间的高斯密度函数，其变量都是向量或者矩阵。式中，$\mu$为中心点，$\sigma$代表此密度函数的协方差矩阵，这些参数决定了函数形状的中心，宽幅，走向等等。

\paragraph
这个式子的含义是$x$事件发生的概率密度，或者说是点$x$在他应在的簇中的概率密度。
则对于$n$个点$X=\{x_1,x_2,\cdots,x_n\}$他们在应属于的簇内的概率密度就可以将这些密度函数相乘：

$$
P(X;\mu,\sigma)=\prod_{i=1}^n g(x_i;\mu,\sigma)
$$

\paragraph
试想，我们的目的是把这些点归属于他们应在的簇内，那么换句话说，就是这些点都大概率在他们的簇内，即让上面的式子取最大值。

\paragraph
我们用$ln$函数简化计算：

$$
J(\mu,\sigma)=ln(P(X;\mu,\sigma))=ln(\prod_{i=1}^n g(x_i;\mu,\sigma))=\sum_{i=1}^nln(g(x_i;\mu,\sigma))
$$
$$
=\sum_{i=1}^n[-\frac{d}{2}ln(2\pi)-\frac{1}{2}ln|\sigma|-\frac{1}{2}(x_i-\mu)^T\sigma^{-1}(x_i-\mu)]
$$
$$
=-\frac{nd}{2}ln(2\pi)-\frac{n}{2}ln|\sigma|-\frac{1}{2}\sum_{i=1}^n[(x_i-\mu)^T\sigma^{-1}(x_i-\mu)]
$$

\paragraph
$J$对$\mu,\sigma$求偏导数：

$$
\frac{\partial J}{\partial \mu}=-\frac{1}{2}\sum_{i=1}^n[\sigma^{-1}\frac{\partial ((x_i-\mu)^T(x_i-\mu))}{\partial \mu}]=\frac{1}{2}\sum_{i=1}^n[\sigma^{-1}\frac{\partial ((x_i-\mu)^T(x_i-\mu))}{\partial (x_i-\mu)}]
$$
$$
=\frac{1}{2}\sum_{i=1}^n[\sigma^{-1} 2(x_i-\mu)]=\sigma^{-1}(\sum_{i=1}^nx_i-n\mu)=0
$$
$$
\iff\mu=\frac{1}{n}\sum_{i=1}^nx_i
$$

$$
\frac{\partial J}{\partial \sigma}=-\frac{n}{2}\frac{\partial ln|\sigma|}{\partial \sigma}-\frac{1}{2}\sum_{i=1}^n\frac{\partial ((x_i-\mu)^T\sigma^{-1}(x_i-\mu))}{\partial \sigma}
$$
$$
=-\frac{n}{2}\sigma^{-1}-\frac{1}{2}\sum_{i=1}^n(\frac{\partial \sigma^{-1}}{\partial \sigma}(x_i-\mu)(x_i-\mu)^T)
$$
$$
=-\frac{n}{2}\sigma^{-1}-\frac{1}{2}\sum_{i=1}^n(\sigma^{-1}\sigma^{-1}(x_i-\mu)(x_i-\mu)^T)=0
$$
$$
\iff
\sigma=\frac{1}{n}\sum_{i=1}^{n}(x_i-\mu)(x_i-\mu)^T
$$

\paragraph
由于高斯聚类适用于点在类椭圆区域的情况，所以要对其进行改进，我们用加权的高斯密度函数来优化（下文以三个加权为例）:

$$
p(x)=\alpha_1g(x;\mu_1,\sigma_1)+\alpha_2g(x;\mu_2,\sigma_2)+\alpha_3g(x;\mu_3,\sigma_3)
$$
其中 
$$
\alpha_1+\alpha_2+\alpha_3=1
$$

\paragraph
令$\sigma=\varsigma^2$，则单一高斯密度函数为：

$$
g(x;\mu,\varsigma^2)=\frac{1}{\sqrt{(2\pi)^d}\varsigma}e^{-\frac{(x-\mu)^T(x-\mu)}{2\varsigma^2}}
$$

\paragraph
则所有点在各自簇内的概率为:

$$
P(X)=\prod_{i=1}^n p(x_i)
$$

\paragraph
则：

$$
J(\theta)=ln[\prod_{i=1}^np(x_i)]
=\sum_{i=1}^nlnp(x_i)=\sum_{i=1}^nln[\alpha_1g(x_i;\mu_1,\varsigma_1^2)+\alpha_2g(x_i;\mu_2,\varsigma_2^2)+\alpha_3g(x_i;\mu_3,\varsigma_3^2)]
$$

\paragraph
利用贝叶斯公式引入符号：

$$
\beta_j(x)=p(j|x)=\frac{p(j\cap x)}{p(x)}=\frac{p(j)p(x|j)}{p(x)}
=\frac{\alpha_jg(x;\mu_j,\varsigma_j^2)}{\alpha_1g(x;\mu_1,\varsigma_1^2)+\alpha_2g(x;\mu_2,\varsigma_2^2)+\alpha_3g(x;\mu_3,\varsigma_3^2)}
$$

\paragraph
对$J$微分（具体计算过程不再给出）：

$$
\frac{\partial J(\theta)}{\partial \mu_j}=\sum_{i=1}^n\beta_j(x_i)(\frac{x_i-\mu_j}{\varsigma_j^2})=0
$$
$$
\frac{\partial J(\theta)}{\partial \varsigma_j}=\sum_{i=1}^n\beta_j(x_i)[\frac{(x_i-\mu_j)^T(x_i-\mu_j)}{\varsigma_j^3}-\frac{d}{\varsigma_j}]=0
$$

\paragraph
得到：

$$
\mu_j=\frac{\sum_{i=1}^n\beta_j(x_i)x_i}{\sum_{i=1}^n\beta_j(x_i)}
$$
$$
\varsigma_j^2=\frac{1}{d}\frac{\sum_{i=1}^n\beta_j(x_i)(x_i-\mu_j)^T(x_i-\mu_j)}{\sum_{i=1}^n\beta_j(x_i)}
$$
\paragraph
以上是$\mu_j，\varsigma_j$让J取极值的条件，但我们还有三个未知数：$\alpha_1,\alpha_2,\alpha_3$

\paragraph
使用拉格朗日乘数法，
构造函数$J_{new}=J+\lambda(1-\alpha_1-\alpha_2-\alpha_3)$，则有：

$$
\frac{\partial J_{new}}{\partial \alpha_j}=\frac{1}{\alpha_j}\sum_{i=1}^n\beta_j(x_i)-\lambda=0
$$
$$
\iff
\begin{cases}
\alpha_1\lambda=\sum_{i=1}^n\beta_1(x_i)\\
\alpha_2\lambda=\sum_{i=1}^n\beta_2(x_i)\\
\alpha_3\lambda=\sum_{i=1}^n\beta_3(x_i)
\end{cases}
$$
\paragraph
三个式子相加：

$$
(\alpha_1+\alpha_2+\alpha_3)\lambda=\sum_{i=1}^n[\beta_1(x_i)+\beta_2(x_i)+\beta_3(x_i)]
$$
$$
\iff
\lambda=\sum_{i=1}^n1=n
$$
$$
\iff
\alpha_j=\frac{1}{n}\sum_{i=1}^n\beta_j(x_i),j=1,2,3
$$

\paragraph
这些结论都不失一般性，即对于欧式空间中的n个点$x_1,x_2,\cdots,x_n$，若高斯混合分量有k个：

$$
\mu_j=\frac{\sum_{i=1}^n\beta_j(x_i)x_i}{\sum_{i=1}^n\beta_j(x_i)}
$$
$$
\varsigma_j^2=\frac{1}{d}\frac{\sum_{i=1}^n\beta_j(x_i)(x_i-\mu_j)^T(x_i-\mu_j)}{\sum_{i=1}^n\beta_j(x_i)}
$$
$$
\alpha_j=\frac{1}{n}\sum_{i=1}^n\beta_j(x_i),j=1,2,\cdots,k
$$

\paragraph
得到高斯混合聚类算法：


\begin{algorithm}[H]
    \caption{高斯混合聚类算法} %算法的名字
    \hspace*{0.02in} {\bf 输入:} %算法的输入， \hspace*{0.02in}用来控制位置，同时利用 \\ 进行换行
    样本集 $D=\{x_1,x_2,\cdots,x_n\}和高斯混合成分个数k$（也是簇的个数）\\
    \hspace*{0.02in} {\bf 过程:}
    \begin{algorithmic}[1]
    \State 初始化高斯混合分布的模型参数$\{(\alpha_j,\mu_j,\sigma_j|1\leq j\leq k\}$\\

    \textbf{Repeat}
    % \State 后写一般语句
    \For{$i=1,2,\cdots,n$} % For 语句，需要和EndFor对应
    　　\State  计算$\beta_j(x_i)
    =\frac{\alpha_jg(x_i;\mu_j,\varsigma_j^2)}{\alpha_1g(x_i;\mu_1,\varsigma_1^2)+\alpha_2g(x_i;\mu_2,\varsigma_2^2)+\alpha_3g(x_i;\mu_3,\varsigma_3^2)}(1 \leq j \leq k)$\\
    \textbf{EndFor}
    \EndFor
    \For{$j=1,2,\cdots,k$} % For 语句，需要和EndFor对应
    　　\State   根据$\mu_j=\frac{\sum_{i=1}^n\beta_j(x_i)x_i}{\sum_{i=1}^n\beta_j(x_i)}$,$\sigma_j=\frac{1}{d}\frac{\sum_{i=1}^n\beta_j(x_i)(x_i-\mu_j)^T(x_i-\mu_j)}{\sum_{i=1}^n\beta_j(x_i)}$,$\alpha_j=\frac{1}{n}\sum_{i=1}^n\beta_j(x_i)$计算新的$\mu_j^{'},\sigma_j^{'},\alpha_j^{'}$\\
    \textbf{EndFor}
    \EndFor
    \State 更新模型参数\\
    \textbf{Until} 满足停止条件
    \State $C_i=\emptyset$
    \For{$i=1,2,\cdots,n$} % For 语句，需要和EndFor对应
    　　\State   根据$l_i=argmax_{j \in \{1,2,\cdots,k\}}(\beta_j(x_i))$确定簇标记，并把$x_i$划入$C_{l_i}$\\
    \textbf{EndFor}
    \EndFor
    \State \Return result C
    \end{algorithmic}
    \hspace*{0.02in} {\bf Output:} %算法的结果输出
    簇划分$C=\{C_1,C_2,\cdots,C_k\}$
    \end{algorithm}

    
	\lstinputlisting[language=python]{./GMM.py}

    \begin{figure}[htbp]
        \centering
        \subfigure[pic1.]{
        \begin{minipage}[t]{0.25\linewidth}
        \centering
        \includegraphics[width=1in]{111.eps}
        %\caption{fig1}
        \end{minipage}%
        }%
        \subfigure[pic2.]{
        \begin{minipage}[t]{0.25\linewidth}
        \centering
        \includegraphics[width=1in]{111.eps}
        %\caption{fig2}
        \end{minipage}%
        }%
        \subfigure[pic3.]{
        \begin{minipage}[t]{0.25\linewidth}
        \centering
        \includegraphics[width=1in]{111.eps}
        %\caption{fig2}
        \end{minipage}
        }%
        \subfigure[pic4.]{
        \begin{minipage}[t]{0.25\linewidth}
        \centering
        \includegraphics[width=1in]{111.eps}
        %\caption{fig2}
        \end{minipage}
        }%
        \centering
        \caption{ pics}
        \end{figure}

\end{document}
